
public class Heap<T extends Comparable<T>>{
  public T[] heap;
  public int SIZE;
  public int count;

  Heap(int size){
    SIZE = size;
    // reference: https://stackoverflow.com/questions/34827626/cannot-be-cast-to-ljava-lang-comparable
    heap = (T[])new Comparable[SIZE];
    count = 0;
  }


  public void add (T item){
    if(count >= SIZE){
      // throw new Exception("Heap Overflow");
      System.out.println("Heap Full");
      return;
    }
    heap[count] = item;
    int childIndex = count;
    count++;

    while(childIndex > 0){
      int parentIndex = (int)Math.floor((childIndex-1)/2);
      T parent = heap[parentIndex];
      if(item.compareTo(parent) > 0){
        heap[parentIndex] = heap[childIndex];
        heap[childIndex] = parent;
      } else {
        break;
      }
      childIndex = parentIndex;
    }
  }

  public void print(){
     System.out.print("[ ");
    for(int i = 0; i < count; i++){
      System.out.print(heap[i] + ", ");
    }
     System.out.println(" ]");

  }
}